import functools


# 究极暴力
# class Solution(object):
#     def minimumMoves(self, arr):
#         """
#         :type arr: List[int]
#         :rtype: int
#         """
#
#         @functools.cache
#         def search(arr):
#             n = len(arr)
#             if n == 0:
#                 return 0
#             if n == 1:
#                 return 1
#
#             @functools.cache
#             def judge(i, j):
#                 if j == i:
#                     return True
#                 else:
#                     if j - i == 1:
#                         return arr[i] == arr[j]
#                     else:
#                         return arr[i] == arr[j] and judge(i + 1, j - 1)
#
#             min_count = n
#             for i in range(n):
#                 for j in range(i, n):
#                     if judge(i, j):
#                         min_count = min(min_count, 1 + search(arr[: i] + arr[j + 1:]))
#             return min_count
#
#         return search(tuple(arr))

class Solution(object):
    def minimumMoves(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        n = len(arr)

        @functools.cache
        def search(i, j):
            if j == i:
                return 1
            if j - i == 1:
                if arr[i] == arr[j]:
                    return 1
                else:
                    return 2
            min_value = j - i + 1
            for k in range(i, j):
                min_value = min(min_value, search(i, k) + search(k + 1, j))
            if arr[i] == arr[j]:
                min_value = min(min_value, search(i + 1, j - 1))
            return min_value

        return search(0, n - 1)


data = Solution()
arr = [1, 3, 4, 1, 5]
print(data.minimumMoves(arr))
arr = [1, 2]
print(data.minimumMoves(arr))
arr = [2, 2, 4, 1, 2, 2, 5]
print(data.minimumMoves(arr))
arr = [4, 1, 14, 16, 15, 18, 19, 17, 10, 8, 10, 4, 19, 17, 14, 17, 2, 1, 14, 11]
print(data.minimumMoves(arr))
